1. Field of the Invention
This invention relates generally to the optical scanning of two-dimensional bar code symbols and in particular to the optical scanning of a randomly oriented two-dimensional bar code symbol by first determining the orientation of the symbol with respect to the field of view of the scanning device and then rotating and moving the field of view accordingly, either manually or automatically, so as to be aligned substantially with the symbol for scanning, further processing and decoding and then fine tuning the alignment automatically.
2. Description of Related Art
Bar codes have become broadly accepted as a means for automatically identifying objects. A bar code symbol is a pattern of parallel bars and spaces of various widths that represent data elements or characters. The bars represent strings of binary ones and the spaces represent strings of binary zeros. Generally, the bars and spaces can be no smaller than a specified minimum width which is called a xe2x80x9cmodulexe2x80x9d or xe2x80x9cunit.xe2x80x9d The bars and spaces are multiples of this module size or minimum width.
The conventional bar code symbol is xe2x80x9cone-dimensionalxe2x80x9d in that the bars and spaces extend only in a single direction. There has been an increasing need, however, for machine-readable symbols that contain more information than conventional bar code symbols. One approach for increasing the information in machine-readable symbols is to reduce the height of the bar codes and stack the bar codes one on top of each other to create a xe2x80x9cstackedxe2x80x9d or xe2x80x9ctwo-dimensionalxe2x80x9d bar code. One such two-dimensional bar code is PDF 417, which was developed by Symbol Technologies, Inc. The PDF417 symbology utilizes a variable number of codewords which are discrete representations of data. A complete description of the PDF417 code is contained in U.S. Pat. No. 5,304,786, which is assigned to the same assignee as the present invention and the AIM Uniform Symbology Specification for PDF417, both of which are incorporated by reference herein. Other two-dimensional bar code symbologies include Code 1 and Maxicode, which are referred to as matrix codes.
Both one-dimensional and two-dimensional bar code symbols are typically read by optical scanning techniques, such as scanning laser beams or CCD scanning, and the resulting electrical signals are then decoded to recover the data encoded in the symbol. In particular, two-dimensional bar code symbols such as those in the PDF417 symbology are advantageously scanned by a two-dimensional rastering laser pattern, which is comprised of a series of horizontal scans repeatedly swept in a vertical direction, as described in U.S. Pat. Nos. 4,816,661 and 5,235,167, which patents are assigned to the assignee of the present application and are incorporated by reference herein. When scanning and decoding a PDF417 bar code symbol, however, the horizontal scan lines of the laser raster must be aligned substantially with the horizontal rows of the symbol, usually within xc2x15xc2x0, as shown in FIG. 1A. In FIG. 1A, the laser scan lines 1 form a field of view and are parallel with the horizontally located rows of PDF417 symbol 3, which will allow successful decoding (in practice, the laser scanning device generates many more closely spaced scan lines 1 than are shown in FIG. 1A, which has been simplified for purposes of clear illustration).
In FIG. 1B, however, the symbol 3a is tilted with respect to the scan lines 1 in the field of view such that the symbol 3a cannot be successfully decoded. Although a two-dimensional bar code such as PDF417 allows some deviation, the orientation of the field of view 1 must still be less than some maximum angle relative to the rows of the symbol.
When using a hand-held laser rastering scanner, the operator can physically align the raster pattern in the field of view with the two-dimensional symbol by rotating the reader and/or the object bearing the symbol until the requisite alignment of the field of view is obtained visually and the symbol is successfully read and decoded. There are many applications, however, in which it is desirable to be able to read and decode a two-dimensional bar code symbol that may be randomly oriented without having to manually move the reader such that the field of view is aligned with rows of the symbol. For example, in an industrial environment, the symbol may be located on an object moving along a conveyor belt where the reader views the symbol from above. Thus, the symbol may be in any orientation relative to the field of view of the reader. In addition, in a retail point-of-sale environment, the symbol may be located on an item presented to a cashier for purchase. The cashier typically puts the item bearing the symbol under a presentation scan lamp, which provides the appropriate laser scanning pattern. It is thus desirable in this situation to allow the cashier to quickly present the item under the scan lamp without having to align the symbol with the raster pattern.
One of the limitations of all the current PDF417 laser scanners is that the scanner must be aligned with the bar code to within about xc2x15xc2x0. Some scanners can produce a raster pattern rotated at any angle. It is also possible to offset that rotated raster pattern in both the x and y direction. Being able to rotate the raster pattern to any angle and offset the pattern in x and y directions, makes it possible to read a PDF417 bar code that is not aligned with the scanner. To make such a system useful it is necessary for the scanner to automatically determine the rotation angle of the bar code as well as the horizontal and vertical offsets, and then produce a raster pattern rotated at the proper angle and offset from center correctly.
The object of the present invention is to describe a system and method for automatically determining the rotation angle as well as the vertical and horizontal offsets of a bar code located within the field of view of the scanner.
It is a further object of the present invention to provide a method and apparatus for reading and decoding a two-dimensional bar code symbol regardless of its orientation with respect to the field of view of the symbol reading device.
It is a further object of the present invention to be able to calculate the angle of skew of the misoriented bar code symbol with respect to the field of view of the reading device in order to correct for the misorientation by rotating the field of view to the calculated angle.
It is still a further object of the present invention to reduce the angle of skew after the scan pattern has been initially aligned, either manually or automatically, to reduce the decode time.
In accordance with these and other objects, provided is a method and apparatus for aligning a scan pattern to a two dimensional bar code having parallel rows of codewords, wherein the two dimensional bar code is scanned with a scanning pattern oriented such that a plurality of lines thereof cross the bar code rows, a determination is made as to if there is a non-zero angle between at least one of the plurality of lines and the rows by decoding codewords in rows intersected by the at least one line and the orientation of the scanning pattern is adjusted to reduce the absolute value of the angle.
The bar code in PDF417 has row indicator codewords in each row and the method can use the decoding of the row indicator codewords read by the at least one line to determine the slope of the angle therefrom. The bar code in PDF417 has codewords which are divided into a plurality of clusters and wherein each row uses codewords of only one cluster and the method can use codewords read by the at least one line to determine the cluster of each codeword and determine the slope of the angle therefrom. The bar code in PDF417 has a fixed number of module widths in each codeword and a row height which is a function of the module width and the number of codewords per row encoded therein and the method can determine the magnitude of the angle from the number of codewords per row and the aspect ratio of the row height to the module width.
The method can repeat the step of determining after a delay following the step of adjusting. The step of scanning comprises initially manually orienting the to the bar code or scanning the bar code with a locating pattern to determine the position of the bar code to initially automatically orient the scanning pattern with respect thereto.
The system for aligning a scan pattern has a pattern generator for generating a scanning pattern oriented to scan the two dimensional bar code such that a plurality of scan lines cross the bar code rows, a processor for determining if there is a non-zero angle between at least one of the plurality of lines and the rows by decoding codewords in rows intersected by the at least one line and an alignment mechanism based upon the determined angle for adjusting the orientation of the scanning pattern generated by the pattern generator to reduce the absolute value of the angle.